package my.jwds.p40;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum2 {

    public static void main(String[] args) {

        Solution obj = new Solution();
        long start = System.currentTimeMillis();
        System.out.println(obj.combinationSum2(new int[]{10,1,2,7,6,1,5},8));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {
        List<List<Integer>> list = new ArrayList<>();
        int []nums = new int[51];
        int target;
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            this.target = target;
            for (int candidate : candidates) {
                nums[candidate] ++;
            }
            dfs(1,0,new ArrayList<>());
            return list;
        }


        void dfs(int index,int sum,List<Integer> item){
            for (int i = index; i < 51; i++) {
                if (sum +i > target)break;
                List<Integer> clone = new ArrayList<>(item);
                int cloneSum = sum;
                for (int j = 0; j < nums[i]; j++) {
                    clone.add(i);
                    cloneSum+= i;
                    if (cloneSum == target){
                        list.add(clone);
                    }
                    if (cloneSum >= target) break;
                    dfs(i+1, cloneSum, clone);
                }
            }
        }

    }
}